Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone
Identifieur interne : 004A28 ( Main/Exploration ); précédent : 004A27; suivant : 004A29Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone
Auteurs : François Charpillet [France] ; Fabrice Lauri [France]Source :
- Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle [ 0992-499X ] ; 2007.
Descripteurs français
Abstract
RÉSUMÉ. Patrouiller dans un environnement implique une équipe d'agents dont le but consiste à visiter continuellement et aussi fréquemment que possible les lieux les plus pertinents. Afin d'obtenir des performances optimales, il est alors primordial que les agents coordonnent leurs actions. De nombreux domaines peuvent être concernés par ce problème, comme la robotique, la simulation ou les jeux vidéo. Nous adoptons dans cet article une approche d'optimisation basée sur les colonies de fourmis pour traiter ce problème. Deux algorithmes sont proposés, dans lesquels des colonies de fourmis sont engagées dans une compétition pour découvrir la meilleure stratégie de patrouille multi-agent. Les résultats expérimentaux montrent que, sur quatre des six graphes étudiés, l'une de nos techniques est significativement meilleure que la technique d'apprentissage par renforcement proposée par Santana. ABSTRACT. Patrolling an environment involves a team of agents whose goal usually consists of continuously visiting its most relevant areas as frequently as possible. For such a task, agents have to coordinate their actions in order to achieve optimal performance. A wide range of applications can be dealt with this problem, from computer network management to vehicle routing. The Ant Colony Optimization is adopted here as the solution approach to this problem. Two novel ACO algorithms are proposed here, in which several ants' colonies try to discover the best multi-agent patrolling strategy. Experimental results show that, for four out of the six evaluated graphs, one of our techniques significantly outperforms the reinforcement learning technique proposed by Santana, irrespective of the number of the involved patrolling agents.
Url:
Affiliations:
- France
- Franche-Comté, Grand Est, Lorraine (région)
- Belfort, Nancy
- Institut national polytechnique de Lorraine, Université Nancy 2, Université de Lorraine, Université de technologie de Belfort-Montbéliard
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 006237
- to stream Hal, to step Curation: 006237
- to stream Hal, to step Checkpoint: 003C09
- to stream Main, to step Merge: 004F23
- to stream Main, to step Curation: 004A28
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone</title><author><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2355" status="OLD"><idno type="RNSR">200218290B</idno><orgName>Autonomous intelligent machine</orgName><orgName type="acronym">MAIA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/maia</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lauri, Fabrice" sort="Lauri, Fabrice" uniqKey="Lauri F" first="Fabrice" last="Lauri">Fabrice Lauri</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-21190" status="OLD"><orgName>Laboratoire Systèmes et Transports</orgName><orgName type="acronym">SET</orgName><desc><address><addrLine>90010 Belfort cedex, France</addrLine><country key="FR"></country></address><ref type="url">http://set.utbm.fr/</ref></desc><listRelation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-302222" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300261" type="direct"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-302222" type="direct"><org type="institution" xml:id="struct-302222" status="VALID"><orgName>Institut de Recherche sur les Transports, l'Energie et la Société - IRTES</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00175666</idno><idno type="halId">inria-00175666</idno><idno type="halUri">https://hal.inria.fr/inria-00175666</idno><idno type="url">https://hal.inria.fr/inria-00175666</idno><date when="2007">2007</date><idno type="wicri:Area/Hal/Corpus">006237</idno><idno type="wicri:Area/Hal/Curation">006237</idno><idno type="wicri:Area/Hal/Checkpoint">003C09</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003C09</idno><idno type="wicri:doubleKey">0992-499X:2007:Charpillet F:optimation:par:colonies</idno><idno type="wicri:Area/Main/Merge">004F23</idno><idno type="wicri:Area/Main/Curation">004A28</idno><idno type="wicri:Area/Main/Exploration">004A28</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone</title><author><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2355" status="OLD"><idno type="RNSR">200218290B</idno><orgName>Autonomous intelligent machine</orgName><orgName type="acronym">MAIA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/maia</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lauri, Fabrice" sort="Lauri, Fabrice" uniqKey="Lauri F" first="Fabrice" last="Lauri">Fabrice Lauri</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-21190" status="OLD"><orgName>Laboratoire Systèmes et Transports</orgName><orgName type="acronym">SET</orgName><desc><address><addrLine>90010 Belfort cedex, France</addrLine><country key="FR"></country></address><ref type="url">http://set.utbm.fr/</ref></desc><listRelation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-302222" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300261" type="direct"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-302222" type="direct"><org type="institution" xml:id="struct-302222" status="VALID"><orgName>Institut de Recherche sur les Transports, l'Energie et la Société - IRTES</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author></analytic><series><title level="j">Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle</title><idno type="ISSN">0992-499X</idno><imprint><date type="datePub">2007</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>ACO</term><term>colonies de fourmis</term><term>multi-agent patrolling</term><term>patrouille multi-agent</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="fr">RÉSUMÉ. Patrouiller dans un environnement implique une équipe d'agents dont le but consiste à visiter continuellement et aussi fréquemment que possible les lieux les plus pertinents. Afin d'obtenir des performances optimales, il est alors primordial que les agents coordonnent leurs actions. De nombreux domaines peuvent être concernés par ce problème, comme la robotique, la simulation ou les jeux vidéo. Nous adoptons dans cet article une approche d'optimisation basée sur les colonies de fourmis pour traiter ce problème. Deux algorithmes sont proposés, dans lesquels des colonies de fourmis sont engagées dans une compétition pour découvrir la meilleure stratégie de patrouille multi-agent. Les résultats expérimentaux montrent que, sur quatre des six graphes étudiés, l'une de nos techniques est significativement meilleure que la technique d'apprentissage par renforcement proposée par Santana. ABSTRACT. Patrolling an environment involves a team of agents whose goal usually consists of continuously visiting its most relevant areas as frequently as possible. For such a task, agents have to coordinate their actions in order to achieve optimal performance. A wide range of applications can be dealt with this problem, from computer network management to vehicle routing. The Ant Colony Optimization is adopted here as the solution approach to this problem. Two novel ACO algorithms are proposed here, in which several ants' colonies try to discover the best multi-agent patrolling strategy. Experimental results show that, for four out of the six evaluated graphs, one of our techniques significantly outperforms the reinforcement learning technique proposed by Santana, irrespective of the number of the involved patrolling agents.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Franche-Comté</li><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Belfort</li><li>Nancy</li></settlement><orgName><li>Institut national polytechnique de Lorraine</li><li>Université Nancy 2</li><li>Université de Lorraine</li><li>Université de technologie de Belfort-Montbéliard</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name></region><name sortKey="Lauri, Fabrice" sort="Lauri, Fabrice" uniqKey="Lauri F" first="Fabrice" last="Lauri">Fabrice Lauri</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004A28 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004A28 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00175666
|texte= Optimation par colonies de fournis d'un essaim de patrouilleurs pour la surveillance de zone
}}
| This area was generated with Dilib version V0.6.33. |  |